{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Non-decreasing Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkPossibility"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #非递减数列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为&nbsp;<code>n</code>&nbsp;的整数数组<meta charset=\"UTF-8\" />&nbsp;<code>nums</code>&nbsp;，请你判断在 <strong>最多 </strong>改变&nbsp;<code>1</code> 个元素的情况下，该数组能否变成一个非递减数列。</p>\n",
    "\n",
    "<p>我们是这样定义一个非递减数列的：&nbsp;对于数组中任意的&nbsp;<code>i</code> <code>(0 &lt;= i &lt;= n-2)</code>，总满足 <code>nums[i] &lt;= nums[i + 1]</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [4,2,3]\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [4,2,1]\n",
    "<strong>输出:</strong> false\n",
    "<strong>解释:</strong> 你不能在只改变一个元素的情况下将其变为非递减数列。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "<meta charset=\"UTF-8\" />\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>5</sup>&nbsp;&lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [non-decreasing-array](https://leetcode.cn/problems/non-decreasing-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [non-decreasing-array](https://leetcode.cn/problems/non-decreasing-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,3]', '[4,2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        # 遇到递减的情况，要么缩小前面的元素，要么放大后面的元素\n",
    "        # 缩小前面的元素时不破坏前面的非递减性，放大后面的元素不破坏后续非递减\n",
    "        N = len(nums)\n",
    "        # 记录变化的次数\n",
    "        count = 0\n",
    "        for i in range(1,N):\n",
    "            if nums[i] < nums[i-1]: # 出现了递减的情况\n",
    "                count += 1\n",
    "                if i == 1 or nums[i] >= nums[i - 2]: # 比往前第一个元素小，比往前第二个元素大\n",
    "                    nums[i - 1] = nums[i] # 尽量修改num[i- 1]，因为nums[i]后面的元素未知\n",
    "                else:\n",
    "                    nums[i] = nums[i - 1] # 调整num[i- 1]会使得nums[i]不满足条件，只能调整nums[i]\n",
    "        return count <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        num = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                num = num + 1\n",
    "                if num > 1:return False\n",
    "                if i == 1 or nums[i] >= nums[i - 2]:\n",
    "                    nums[i-1] = nums[i]\n",
    "                else:\n",
    "                    nums[i] = nums[i-1]\n",
    "        return num<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        # n = len(nums)\n",
    "        N = len(nums)\n",
    "        count = 0\n",
    "        for i in range(1, N):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                count += 1\n",
    "                if i == 1 or nums[i] >= nums[i - 2]:\n",
    "                    nums[i - 1] = nums[i]\n",
    "                else:\n",
    "                    nums[i] = nums[i - 1]\n",
    "        return count <= 1\n",
    "\n",
    "        # if n <= 2:\n",
    "        #     return True\n",
    "        # peak = 0\n",
    "        # if nums[0] > nums[1]:\n",
    "        #     peak += 1\n",
    "        #     nums[0] = nums[1]\n",
    "        # for i in range(1,n-1):\n",
    "        #     if (nums[i] > nums[i-1] and nums[i] > nums[i+1]) or (nums[i] < nums[i-1] and nums[i] <= nums[i+1]):\n",
    "        #         peak += 1\n",
    "        #         if peak > 1:\n",
    "        #             return False\n",
    "        #         nums[i] = nums[i-1]\n",
    "        #         # print(nums)\n",
    "        # if nums[-1] < nums[-2]:\n",
    "        #     peak += 1\n",
    "        #     if peak > 1:\n",
    "        #         return False\n",
    "        # return True\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        N =len(nums)\n",
    "        count = 0\n",
    "        for i in range(1,N):\n",
    "            if nums[i]<nums[i-1]:\n",
    "                count +=1\n",
    "                if i==1 or nums[i]>=nums[i-2]:\n",
    "                    nums[i-1]=nums[i]\n",
    "                else:\n",
    "                    nums[i]=nums[i-1]\n",
    "        return count<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        pos = 0\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            if nums[i] < nums[i-1]:\n",
    "                pos += 1\n",
    "        if pos > 1:\n",
    "            return False\n",
    "        if pos == 1:\n",
    "            for i in range(n):\n",
    "                temp = nums[:i] + nums[i+1:]\n",
    "                t1 = temp[:]\n",
    "                t1.sort()\n",
    "                if temp == t1:\n",
    "                    return True\n",
    "        if pos == 0:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        changed = False\n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i] <= nums[i+1]:\n",
    "                continue\n",
    "            elif changed:\n",
    "                return False\n",
    "            else:\n",
    "                if i == 0 or nums[i-1] <= nums[i+1]:\n",
    "                    nums[i] = nums[i+1]\n",
    "                else:\n",
    "                    nums[i+1] = nums[i]\n",
    "            changed = True\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        change = 0\n",
    "        left ,right = 0, 1\n",
    "        while right <= n-1 and change < 2:\n",
    "            if nums[left] > nums[right]:\n",
    "                if left == 0 or right == n-1:\n",
    "                    change += 1\n",
    "                elif nums[left-1] > nums[right] and nums[left] > nums[right+1]:\n",
    "                    return False\n",
    "                else:\n",
    "                    change += 1\n",
    "            left += 1\n",
    "            right += 1\n",
    "        \n",
    "        if change < 2:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "            N = len(nums)\n",
    "            count = 0\n",
    "            for i in range(1, N):\n",
    "                if nums[i] < nums[i - 1]:\n",
    "                    count += 1\n",
    "                    if i == 1 or nums[i] >= nums[i - 2]:\n",
    "                        nums[i - 1] = nums[i]\n",
    "                    else:\n",
    "                        nums[i] = nums[i - 1]\n",
    "            return count <= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for i in range(1, n):\n",
    "            if nums[i] <nums[i - 1]:\n",
    "                count += 1\n",
    "                if i > 1 and nums[i] < nums[i - 2]:                    \n",
    "                    nums[i] = nums[i - 1]\n",
    "        return count <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        zero = nums[0]   #不改一个数的最后一个值\n",
    "        one = 0          #改一个值后的最后一个数的最小值\n",
    "        for i in range(1, n):\n",
    "            \n",
    "            if nums[i] >= zero:\n",
    "                zeroNew = nums[i]\n",
    "            else:\n",
    "                zeroNew = inf\n",
    "\n",
    "            oneNew = inf\n",
    "            #不改最后一个数\n",
    "            if nums[i] >= one:\n",
    "                oneNew = nums[i]\n",
    "            #改最后一个数\n",
    "\n",
    "            oneNew = min(oneNew, zero)\n",
    "\n",
    "            if oneNew == inf:\n",
    "                return False\n",
    "\n",
    "            zero, one = zeroNew, oneNew    \n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                        \n",
    "\n",
    "                \n",
    "\n",
    "                    \n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        def check(nums,signal):\n",
    "            n = len(nums)\n",
    "            temp = nums[0]\n",
    "            k = 0\n",
    "            for i in range(1,n):\n",
    "                if signal*nums[i] >= signal*temp:\n",
    "                    temp = nums[i]\n",
    "                    continue\n",
    "                else:\n",
    "                    k+=1\n",
    "                    if k==2:\n",
    "                        return False\n",
    "                    else:\n",
    "                        continue\n",
    "            return True\n",
    "\n",
    "        nums_reverse = nums[::-1]\n",
    "        return check(nums,1) or check(nums_reverse,-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        # 只能修改一次\n",
    "        # 当从前往后搜索的时候，当发现逆序对的时候，有两种修改方式，第一是修改前面的值，第二是修改后面的值，看看有几次要修改\n",
    "        count = 0\n",
    "        nums.insert(0,-inf)\n",
    "        nums.append(inf)\n",
    "        for i in range(1,len(nums)-1):\n",
    "            if nums[i] > nums[i+1]:\n",
    "                count += 1\n",
    "                # 修改前面的,可以吗？\n",
    "                if nums[i-1] <= nums[i+1]:\n",
    "                    nums[i] = nums[i+1]\n",
    "                    continue \n",
    "                # 修改后面的可以吗？\n",
    "                # 修改前面不成功，只能修改后面\n",
    "                nums[i+1] = nums[i]\n",
    "        return count <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        当 a[i] > a[i + 1] 时：\n",
    "        ... <= a[i - 2] <= a[i - 1] <= a[i] > a[i + 1] <= a[i + 2] <= ...\n",
    "\n",
    "        1. a[i] -> a[i + 1]\n",
    "            ... <= a[i - 2] <= a[i - 1] <= a[i] ？ a[i + 2] <= a[i + 2] <= ...\n",
    "        2. a[i] -> a[i - 1]\n",
    "            ... <= a[i - 2] <= a[i - 1] <= a[i - 1] ? a[i + 1] <= a[i + 2] <= ...\n",
    "        \n",
    "        a[i] > a[i + 2] && a[i - 1] > a[i + 1]\n",
    "        \n",
    "        \"\"\"\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        if n <= 2:\n",
    "            return True\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(n - 1):\n",
    "            if nums[i] > nums[i + 1]:\n",
    "                if ((i + 2 < n and nums[i] > nums[i + 2]) and \n",
    "                    (i - 1 >= 0 and nums[i - 1] > nums[i + 1])):\n",
    "                    return False\n",
    "                cnt += 1\n",
    "\n",
    "        return cnt <= 1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            # 需要进行操作。\n",
    "            if nums[i] < nums[i-1]:\n",
    "                cnt += 1\n",
    "                # 如果是前两个（i==1）,或第三个大于等于第一个，直接把中间那个换了。\n",
    "                # 不要动 nums[i] ，因为nums[i]后面的元素是啥我们还不知道呢，少动它为妙。\n",
    "                if i == 1 or nums[i] >= nums[i - 2]:\n",
    "                    nums[i-1] = nums[i] # 前面缩小\n",
    "                # 如果第三个小于第一个，那么动第3个，比如3，4，2\n",
    "                else:\n",
    "                    nums[i] = nums[i-1] # 后面放大\n",
    "        return cnt <= 1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        count = 0\n",
    "        length = len(nums)\n",
    "        for i in range(1, length):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                count += 1\n",
    "                if i + 1 < length and i - 2 >= 0:\n",
    "                    if nums[i + 1] < nums[i - 1] and nums[i - 2] > nums[i]:\n",
    "                        return False\n",
    "            if count > 1:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        N = len(nums)\n",
    "        count = 0\n",
    "        for i in range(1, N):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                count += 1\n",
    "                if i == 1 or nums[i] >= nums[i - 2]:\n",
    "                    nums[i - 1] = nums[i]\n",
    "                else:\n",
    "                    nums[i] = nums[i - 1]\n",
    "        return count <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        N = len(nums)\n",
    "        count = 0\n",
    "        for i in range(1, N):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                count += 1\n",
    "                if i == 1 or nums[i] >= nums[i - 2]:\n",
    "                    nums[i - 1] = nums[i]\n",
    "                else:\n",
    "                    nums[i] = nums[i - 1]\n",
    "        return count <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        big1 = float('-inf') #第一大\n",
    "        big2 = float('-inf') #第二大\n",
    "        cnt = 0\n",
    "        for i in range(len(nums)):\n",
    "            if(nums[i] >= big1):\n",
    "                big2 = big1\n",
    "                big1 = nums[i]\n",
    "            elif(big2 <= nums[i] < big1 and cnt == 0):\n",
    "                cnt += 1\n",
    "                big1 = nums[i]\n",
    "            elif(nums[i] < big2 and cnt == 0):\n",
    "                cnt += 1\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        count = 0\n",
    "        flag = True\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] > nums[i+1]:\n",
    "                count += 1\n",
    "                if i > 0:\n",
    "                    if nums[i-1] <= nums [i+1]:\n",
    "                        nums[i] = nums[i-1]\n",
    "                    else:\n",
    "                        nums[i+1] = nums[i]\n",
    "            if count >= 2:\n",
    "                flag = False\n",
    "                break\n",
    "        return flag\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "\n",
    "        count = 0\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                count += 1\n",
    "\n",
    "                if i == 1 or nums[i] >= nums[i - 2]:\n",
    "                    nums[i - 1] = nums[i]\n",
    "                else:\n",
    "                    nums[i] = nums[i - 1]\n",
    "\n",
    "        if count >= 2:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        k=0\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] > nums[i+1]:\n",
    "                if (i < len(nums)-2) and (nums[i] < nums[i+2]):\n",
    "                    nums[i+1] = nums[i]\n",
    "                elif i == len(nums)-2:\n",
    "                    nums[i+1] = nums[i]\n",
    "\n",
    "                else:\n",
    "                    nums[i] = nums[i+1]\n",
    "                    if i > 0:\n",
    "                        if nums[i] < nums[i-1]:\n",
    "                            return False\n",
    "\n",
    "                k +=1\n",
    "        if k>1:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        ans = 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i] > nums[i + 1]:\n",
    "                ans += 1\n",
    "                if i == 0 or nums[i - 1] <= nums[i + 1]:\n",
    "                    nums[i] = nums[i + 1]\n",
    "                else:\n",
    "                    nums[i + 1] = nums[i]\n",
    "                \n",
    "        return ans <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        changed = False\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                if changed:\n",
    "                    return False\n",
    "                if i > 1 and nums[i] < nums[i - 2]:\n",
    "                    nums[i] = nums[i - 1]\n",
    "                changed = True\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        a = []\n",
    "        for x in nums:\n",
    "            p = bisect_right(a, x)\n",
    "            if p != len(a): a[p] = x\n",
    "            else: a.append(x)\n",
    "        return n - len(a) <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: list[int]) -> bool:\n",
    "        count = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] < nums[i-1]:\n",
    "                if i <= len(nums)-2 and nums[i] < nums[i-2] and nums[i+1] < nums[i-1] and i-2 >= 0:\n",
    "                    count += 1\n",
    "                count +=1\n",
    "        if count > 1:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPossibility(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        N = len(nums)\n",
    "        count = 0\n",
    "        for i in range(1, N):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                count += 1\n",
    "                if i == 1 or nums[i] >= nums[i - 2]:\n",
    "                    nums[i - 1] = nums[i]\n",
    "                else:\n",
    "                    nums[i] = nums[i - 1]\n",
    "        return count <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "\n",
    "        count = 0\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                count += 1\n",
    "\n",
    "                if i == 1 or nums[i] >= nums[i - 2]:\n",
    "                    nums[i - 1] = nums[i]\n",
    "                else:\n",
    "                    nums[i] = nums[i - 1]\n",
    "\n",
    "        if count >= 2:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        flag=1\n",
    "        nums=[-1e-6]+nums\n",
    "        for i in range(1,len(nums)-1):\n",
    "            if nums[i]>nums[i+1]:\n",
    "                if flag:\n",
    "                    if nums[i+1]>=nums[i-1]:\n",
    "                        nums[i]=nums[i-1]\n",
    "                    else:\n",
    "                        nums[i+1]=nums[i]\n",
    "                    flag=0\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for i in range(0,n-1):\n",
    "            x,y = nums[i],nums[i+1]\n",
    "            if x > y:\n",
    "                count += 1\n",
    "                if count > 1:\n",
    "                    return False\n",
    "                if i>0 and y < nums[i-1]:\n",
    "                    nums[i+1] = x\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        n = 0\n",
    "        if len(nums) >= 2 and nums[1]< nums[0]:\n",
    "            nums[0] = nums[1]\n",
    "            n += 1\n",
    "        for i in range(2,len(nums)):\n",
    "            pre = nums[i-2]\n",
    "            cur = nums[i-1]\n",
    "            nxt = nums[i]\n",
    "            if cur > nxt:\n",
    "                if nxt >= pre:\n",
    "                    nums[i - 1] = pre\n",
    "                    n += 1\n",
    "                else:\n",
    "                    nums[i] = cur\n",
    "                    n += 1\n",
    "            if n > 1:\n",
    "                return False\n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        n = len(nums)\n",
    "        idxs = [i for i in range(n-1) if nums[i] > nums[i+1]]\n",
    "        if not idxs:\n",
    "            return True\n",
    "        if len(idxs) >= 2:\n",
    "            return False\n",
    "        l, r = idxs[0], idxs[0] + 1\n",
    "        if not l or nums[l-1] <= nums[r]:\n",
    "            return True\n",
    "        if r == n-1 or nums[l] <= nums[r+1]:\n",
    "            return True\n",
    "        return False\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        change = False\n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i] > nums[i + 1]:\n",
    "                if i > 0 and nums[i - 1] > nums[i + 1]:\n",
    "                    nums[i + 1] = nums[i]\n",
    "                else:\n",
    "                    nums[i] = nums[i + 1]\n",
    "                if change:\n",
    "                    return False\n",
    "                change = True \n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        count = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] < nums[i-1]:\n",
    "                count += 1\n",
    "                if i+1 < len(nums) and i-2 >= 0:\n",
    "                    if nums[i+1] < nums[i-1] and nums[i-2] > nums[i]:\n",
    "                        return False\n",
    "            if count > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        count = 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i] > nums[i + 1]:\n",
    "                if i > 0 and nums[i-1] > nums[i+1]:\n",
    "                    nums[i+1] = nums[i]\n",
    "                count += 1\n",
    "                if count > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        count = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                count += 1\n",
    "                if i == 1 or nums[i] >= nums[i - 2]:\n",
    "                    nums[i - 1] = nums[i]\n",
    "                else:\n",
    "                    nums[i] = nums[i - 1]\n",
    "        return count <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        count = 0\n",
    "        n = len(nums)\n",
    "        for i in range(1,n):\n",
    "            if nums[i] < nums[i-1]:\n",
    "                count += 1\n",
    "                if i == 1 or nums[i] >= nums[i-2]:\n",
    "                    nums[i-1] = nums[i] \n",
    "                else:\n",
    "                    nums[i] = nums[i-1]\n",
    "        return count <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        count = 0\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                count += 1\n",
    "\n",
    "                if i == 1 or nums[i] >= nums[i - 2]:\n",
    "                    nums[i - 1] = nums[i]\n",
    "                else:\n",
    "                    nums[i] = nums[i - 1]\n",
    "        \n",
    "        if count >= 2:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        decrease, idx = 0, 0\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] > nums[i+1]:\n",
    "                decrease += 1\n",
    "                idx = i+1\n",
    "        if not decrease or (decrease == 1 and (idx == len(nums)-1 or idx-1 == 0)): return True\n",
    "        if decrease > 1: return False\n",
    "        if nums[idx+1]<nums[idx-1] and nums[idx]<nums[idx-2]: \n",
    "            return False\n",
    "        else: \n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for i in range(n - 1):\n",
    "            if nums[i] > nums[i+1]:\n",
    "                count += 1\n",
    "                if count > 1: return False\n",
    "                if i > 0 and nums[i + 1] < nums[i - 1]:\n",
    "                    nums[i + 1] = nums[i]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        for i in range(n-1):\n",
    "            x=nums[i]\n",
    "            y=nums[i+1]\n",
    "            if x>y:\n",
    "                nums[i]=y\n",
    "                if self.process(nums):\n",
    "                    return True\n",
    "                nums[i]=x\n",
    "                nums[i+1]=x\n",
    "                return self.process(nums)\n",
    "        return True\n",
    "    def process(self, nums):\n",
    "        n = len(nums)\n",
    "        for i in range(1,n):\n",
    "            if nums[i-1]>nums[i]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "      \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        # 遍历一遍数组,数组长度最少为2\n",
    "        j = 0 # 定义拐点出现的次数\n",
    "        for i in range(len(nums)-1):\n",
    "            # i定义为数组拐点\n",
    "            if nums[i] > nums[i+1]:\n",
    "                j += 1\n",
    "                if j >= 2:\n",
    "                    return False # j一旦到2说明无法完成任务\n",
    "                if i>=1 and nums[i-1]>nums[i+1]: #如果拐点前数字大于拐点后数字，那么对拐点后数字进行上移\n",
    "                    nums[i+1] = nums[i]\n",
    "                else: #如果拐点前数字小于等于拐点后数字，那么对拐点数字进行下移\n",
    "                    #否则的话需要对拐点进行下移，（如果直接对拐点后的数字进行上移容易造成拐点无法消除）\n",
    "                    nums[i] = nums[i+1]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        count = 0  # 记录需要改变的次数\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                count += 1\n",
    "\n",
    "                # 当出现需要改变的情况时，需要判断如何改变\n",
    "                if i >= 2 and nums[i] < nums[i - 2]:\n",
    "                    # 例如，[3, 4, 2, 3]\n",
    "                    # 如果 nums[i] < nums[i - 2]，那么应该将 nums[i] 变得更大\n",
    "                    nums[i] = nums[i - 1]\n",
    "                else:\n",
    "                    # 否则，将 nums[i - 1] 变得更小\n",
    "                    nums[i - 1] = nums[i]\n",
    "\n",
    "        # 最多可以改变一次，因此 count <= 1 时返回 True，否则返回 False\n",
    "        return count <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        count = 0\n",
    "        nums.insert(0,-inf)\n",
    "        nums.append(inf)\n",
    "        for i in range(1,len(nums)-1):\n",
    "            if nums[i] > nums[i+1]:\n",
    "                count += 1\n",
    "                if nums[i-1] <= nums[i+1]:\n",
    "                    nums[i] = nums[i+1]\n",
    "                    continue \n",
    "                nums[i+1] = nums[i]\n",
    "        return count <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        c, n = 0, len(nums)\n",
    "        for i in range(1, n):\n",
    "            if nums[i-1] > nums[i]: \n",
    "                c+=1\n",
    "                if i == 1 or nums[i] >= nums[i-2]: \n",
    "                    nums[i-1] = nums[i]\n",
    "                else: \n",
    "                    nums[i] = nums[i-1]\n",
    "        return c <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        # 有任意一个nums[i-1]>nums[i]，则不是递减数列\n",
    "        def isSorted(nums):\n",
    "            for i in range(1, len(nums)):\n",
    "                if nums[i - 1] > nums[i]:\n",
    "                    return False \n",
    "            return True \n",
    "        if len(nums) <= 1:\n",
    "            return True \n",
    "        for i in range(len(nums)-1):\n",
    "            x = nums[i]\n",
    "            y = nums[i + 1]\n",
    "            if x > y:\n",
    "                nums[i] = y\n",
    "                if isSorted(nums):\n",
    "                    return True\n",
    "                nums[i] = x \n",
    "                nums[i + 1] = x\n",
    "                return isSorted(nums)\n",
    "        return True \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        cnt = 0\n",
    "        pre = float('-inf')\n",
    "\n",
    "        def checkposs(nums,cnt,pre):\n",
    "            if len(nums)==0:\n",
    "                return True\n",
    "            for i in range(len(nums)-1):\n",
    "                if nums[i]>nums[i+1]:\n",
    "                    if cnt:        \n",
    "                        if nums[i+1]>=pre:\n",
    "                            a = checkposs(nums[i+1:],cnt-1,pre)\n",
    "                        else:\n",
    "                            a=False\n",
    "                        if a:\n",
    "                            return a\n",
    "                        nums[i+1]=nums[i]\n",
    "                        b = checkposs(nums[i+1:],cnt-1,nums[i])\n",
    "                        return b \n",
    "                    else:\n",
    "                        return False\n",
    "                pre = nums[i]\n",
    "            return True\n",
    "\n",
    "        return checkposs(nums,1,pre)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def three(self, a, b, c):\n",
    "        if a <= b and b <= c:\n",
    "            return 0\n",
    "        elif a <= b and b > c and a <= c:\n",
    "            return 1\n",
    "        elif a > b and a <= c:\n",
    "            b = a\n",
    "            return 1\n",
    "        elif a > b and a > c:\n",
    "            return 2\n",
    "        else:\n",
    "            return 0\n",
    "    \n",
    "    \n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        a = 0\n",
    "        n = len(nums)\n",
    "        nums.insert(0, - 10**5)\n",
    "        nums.append(10**5)\n",
    "        for i in range(n):\n",
    "            a += self.three(nums[i], nums[i+1], nums[i+2])\n",
    "            if a == 1:\n",
    "                nums[i+1] = nums[i]\n",
    "            elif a >= 2:   \n",
    "                # print(nums)\n",
    "                return False\n",
    "        return True\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "         \n",
    "        cnt = 0 \n",
    "        for i in range(1,len(nums)):\n",
    "             if nums[i] < nums[i-1]:\n",
    "                cnt = cnt +1\n",
    "                if cnt > 1 : return False\n",
    "                if i-2 >= 0  and nums[i] < nums[i-2]:\n",
    "                    nums[i] = nums[i-1]\n",
    "                else:\n",
    "                    nums[i-1] = nums[i]\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        cnt = 0\n",
    "        pre = float('-inf')\n",
    "\n",
    "        def checkposs(nums,cnt,pre):\n",
    "            if len(nums)==0:\n",
    "                return True\n",
    "            for i in range(len(nums)-1):\n",
    "                if nums[i]>nums[i+1]:\n",
    "                    if cnt:        \n",
    "                        if nums[i+1]>=pre:\n",
    "                            a = checkposs(nums[i+1:],cnt-1,pre)\n",
    "                        else:\n",
    "                            a=False\n",
    "                        if a:\n",
    "                            return a\n",
    "                        nums[i+1]=nums[i]\n",
    "                        b = checkposs(nums[i+1:],cnt-1,nums[i])\n",
    "                        return b \n",
    "                    else:\n",
    "                        return False\n",
    "                pre = nums[i]\n",
    "            return True\n",
    "\n",
    "        #return checkposs(nums,1,pre)\n",
    "        cnt=1\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]<nums[i-1]:\n",
    "                if cnt==0:\n",
    "                    return False\n",
    "                else:\n",
    "                    if i==1 or nums[i]>=nums[i-2]:\n",
    "                        nums[i-1]=nums[i]\n",
    "                    else:\n",
    "                        nums[i]=nums[i-1]\n",
    "                    cnt-=1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        if len(nums) <=1:\n",
    "            return True\n",
    "        flag = (nums[0] <= nums[1])\n",
    "        for i in range(1,len(nums)-1):\n",
    "            if nums[i]>nums[i+1]:\n",
    "                if flag:\n",
    "                    if nums[i+1]>=nums[i-1]:\n",
    "                        nums[i] = nums[i + 1]\n",
    "                    else:\n",
    "                        nums[i+1] = nums[i]\n",
    "                    flag = False\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        count = 0\n",
    "        while i < n-1:\n",
    "            if nums[i+1] < nums[i]:\n",
    "                count += 1\n",
    "                if i == 0 or nums[i+1] >= nums[i-1]:\n",
    "                    nums[i] = nums[i+1]\n",
    "                else:\n",
    "                    nums[i+1] = nums[i]\n",
    "            i += 1\n",
    "        return count <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        flag = True\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        while i < n - 1:\n",
    "            if nums[i] <= nums[i + 1]:\n",
    "                i += 1\n",
    "            elif flag:\n",
    "                if i + 2 == n or nums[i] <= nums[i + 2]:\n",
    "                    i += 2\n",
    "                elif i - 1 == -1 or nums[i - 1] <= nums[i + 1]:\n",
    "                    i += 1\n",
    "                flag = False\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        if len(nums) == 1:\n",
    "            return True\n",
    "\n",
    "        cnt = 0\n",
    "        idx = 0\n",
    "        while idx < len(nums):\n",
    "            if idx == 0 and nums[idx] > nums[idx + 1]:\n",
    "                cnt +=1 \n",
    "                nums[idx] = nums[idx + 1]\n",
    "            elif idx > 0 and nums[idx] < nums[idx - 1]:\n",
    "                cnt += 1\n",
    "                nums[idx] = nums[idx - 1]\n",
    "            elif 0 < idx < len(nums) - 1 and nums[idx] > max(nums[idx - 1], nums[idx + 1]):\n",
    "                if nums[idx - 1] <= nums[idx + 1]:\n",
    "                    nums[idx] = nums[idx - 1]\n",
    "                    cnt += 1\n",
    "            idx += 1\n",
    "            if cnt > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\r\n",
    "        if len(nums) < 3:\r\n",
    "            return True\r\n",
    "        else:\r\n",
    "            modify = 0\r\n",
    "            for i in range(len(nums) - 1):\r\n",
    "                if nums[i] > nums[i+1]:\r\n",
    "                    modify += 1\r\n",
    "                    if i > 0 and nums[i-1] > nums[i+1]:\r\n",
    "                        nums[i+1] = nums[i]\r\n",
    "                    else:\r\n",
    "                        nums[i] = nums[i+1]\r\n",
    "                if modify > 1:  \r\n",
    "                    return False\r\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for i in range(1, n):\n",
    "            if nums[i] < nums[i-1]:\n",
    "                count += 1\n",
    "                if i == 1 or nums[i] >= nums[i-2]:\n",
    "                    nums[i-1] = nums[i]\n",
    "                else:\n",
    "                    nums[i] = nums[i-1]\n",
    "        return count <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        count = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] < nums[i-1]:\n",
    "                count += 1\n",
    "                if i==1 or nums[i]>=nums[i-2]:\n",
    "                    nums[i-1] = nums[i]\n",
    "                else:\n",
    "                    nums[i] = nums[i-1]\n",
    "        return count<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        temp_i = 0\n",
    "        temp_index = 0\n",
    "        for i in range(n-1):\n",
    "            if nums[i] > nums[i+1]:\n",
    "                temp_i = nums[i]\n",
    "                temp_index = i\n",
    "                nums[i] = nums[i+1]\n",
    "                break\n",
    "        flag1 = True\n",
    "        for i in range(n-1):\n",
    "            if nums[i] > nums[i+1]:\n",
    "                flag1 = False\n",
    "        if flag1:\n",
    "            return flag1\n",
    "        flag2 = True\n",
    "        nums[temp_index] = temp_i\n",
    "        nums[temp_index + 1] = temp_i\n",
    "        for i in range(n-1):\n",
    "            if nums[i] > nums[i+1]:\n",
    "                flag2 = False\n",
    "        return flag2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        cnt = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            x = nums[i]\n",
    "            y = nums[i+1]\n",
    "            if x > y:\n",
    "                cnt += 1\n",
    "                if cnt > 1:\n",
    "                    return False\n",
    "                if i > 0 and y < nums[i-1]:\n",
    "                    nums[i+1] = x\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for i in range(1,n):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                count += 1\n",
    "                if i == 1 or nums[i] >= nums[i - 2]:\n",
    "                    nums[i - 1] = nums[i]\n",
    "                else:\n",
    "                    nums[i] = nums[i - 1]\n",
    "        return count <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        c,d=0,0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i-1]>nums[i]:\n",
    "                c+=1\n",
    "                if(c>1):\n",
    "                    return False\n",
    "                d=i-1\n",
    "        if d<len(nums)-2 and d>0:\n",
    "            if nums[d]>nums[d+2] and nums[d-1]>nums[d+1]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPossibility(self, nums):\n",
    "        N = len(nums)\n",
    "        count = 0\n",
    "        for i in range(1, N):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                count += 1\n",
    "                if i == 1 or nums[i] >= nums[i - 2]:\n",
    "                    nums[i - 1] = nums[i]\n",
    "                else:\n",
    "                    nums[i] = nums[i - 1]\n",
    "        return count <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPossibility(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for i in range(1, n):\n",
    "            if nums[i] < nums[i - 1]:\n",
    "                count += 1\n",
    "                if i==1 or nums[i]>=nums[i-2]:\n",
    "                    nums[i-1]=nums[i]\n",
    "                else:\n",
    "                    nums[i]=nums[i-1]\n",
    "        return count<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        count = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i-1] > nums[i]:\n",
    "                count += 1\n",
    "                if i+1 < len(nums) and i - 2 >= 0:\n",
    "                    if nums[i+1] < nums[i-1] and nums[i-2] > nums[i]:\n",
    "                        return False\n",
    "                if count > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        for i in range(1,n):\n",
    "            if nums[i]<nums[i-1]:\n",
    "                if i ==1:\n",
    "                    nums[i-1]=nums[i]\n",
    "                if i >1:\n",
    "                    if nums[i]<nums[i-2]:\n",
    "                        nums[i]=nums[i-1]\n",
    "                    else:\n",
    "                        nums[i-1]=nums[i]\n",
    "                break\n",
    "        for i in range(1,n):\n",
    "            if nums[i]<nums[i-1]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        cnt = 0 \n",
    "        if len(nums) <= 1:\n",
    "            return True \n",
    "        for i in range(len(nums)-1):\n",
    "            x = nums[i]\n",
    "            y = nums[i + 1]\n",
    "            if x > y:\n",
    "                cnt += 1\n",
    "                if cnt > 1:\n",
    "                    return False \n",
    "                if i > 0 and nums[i - 1] > y:\n",
    "                    nums[i + 1] = x \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def checkPossibility(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        res = True\n",
    "        flag = 0\n",
    "        b = nums.copy()\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if nums[i] > nums[i+1]:\n",
    "                flag += 1\n",
    "                nums[i] = nums[i+1]\n",
    "        if flag <= 1:\n",
    "            return True\n",
    "        flag = 0\n",
    "        for i in range(1,n):\n",
    "            if b[i] < b[i-1]:\n",
    "                flag += 1\n",
    "                b[i] = b[i-1]\n",
    "        if flag <= 1:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        当 a[i] > a[i + 1] 时：\n",
    "        ... <= a[i - 2] <= a[i - 1] <= a[i] > a[i + 1] <= a[i + 2] <= ...\n",
    "        \n",
    "        有两种修改方式：\n",
    "        1. a[i + 1] -> a[i + 2]\n",
    "            ... <= a[i - 2] <= a[i - 1] <= a[i] ? a[i + 2] <= a[i + 2] <= ...\n",
    "        2. a[i] -> a[i - 1]\n",
    "            ... <= a[i - 2] <= a[i - 1] <= a[i - 1] ? a[i + 1] <= a[i + 2] <= ...\n",
    "        \n",
    "        于是，当 a[i] > a[i + 2] && a[i - 1] > a[i + 1] 时，\n",
    "        最多修改一个元素地情况下，数组一定不能变成一个非递减数列，直接 return False\n",
    "        否则，修改次数加一，cnt += 1\n",
    "        最终，当修改次数不超过 1 时，则能变成非递减数列，否则，不能\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        if n <= 2:\n",
    "            return True\n",
    "\n",
    "        cnt = 0 # 修改次数\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            if nums[i] > nums[i + 1]:\n",
    "                if ((i + 2 < n and nums[i] > nums[i + 2]) and \n",
    "                    (i - 1 >= 0 and nums[i - 1] > nums[i + 1])):\n",
    "                    return False\n",
    "                \n",
    "                cnt += 1\n",
    "\n",
    "        return cnt <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        flag = False\n",
    "        ans = 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            cur = nums[i]\n",
    "            if cur > nums[i + 1]:\n",
    "                if flag:\n",
    "                    return False\n",
    "                else:\n",
    "                    ans = i\n",
    "                    flag = True\n",
    "        if ans == 0:\n",
    "            return True\n",
    "        else:\n",
    "            if (not (ans +2 == len(nums))) and (nums[ans] > nums[ans + 2] and nums[ans - 1] > nums[ans + 1]):\n",
    "                return False\n",
    "            else:\n",
    "                return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        numsCopy, i, count = nums[:], 0, 0\n",
    "        while i < len(numsCopy) - 1:\n",
    "            if numsCopy[i] > numsCopy[i + 1]:\n",
    "                count += 1\n",
    "                if count > 1:\n",
    "                    return False\n",
    "\n",
    "                if i != 0 and numsCopy[i - 1] > numsCopy[i + 1]:\n",
    "                    numsCopy[i + 1] = numsCopy[i]\n",
    "                else:\n",
    "                    numsCopy[i] = numsCopy[i + 1]\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        pre = nums[0]\n",
    "        ans = 0\n",
    "        idx = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if num - pre < 0:\n",
    "                ans += 1\n",
    "                idx = i\n",
    "            pre = num\n",
    "        if ans == 0:\n",
    "            return True\n",
    "        elif ans > 1:\n",
    "            return False\n",
    "        else:\n",
    "            if idx == 1 or idx == len(nums) - 1:\n",
    "                return True\n",
    "            elif nums[idx - 2] <= nums[idx] or nums[idx - 1] <= nums[idx + 1]:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "        count = 0\n",
    "        leng = len(nums)\n",
    "        prior_max = -100000\n",
    "        for i in range(leng-1):\n",
    "            if count > 1:\n",
    "                break\n",
    "            if nums[i] > nums[i + 1]:\n",
    "                count += 1\n",
    "                if (i and nums[i-1] > nums[i+1]) and (i+1 != leng-1 and nums[i] > nums[i +2]):\n",
    "                    count += 1\n",
    "                    break\n",
    "        if count <= 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums: List[int]) -> bool:\n",
    "       \n",
    "        n = len(nums)\n",
    "        if n==1 or n==2:\n",
    "            return True\n",
    "        slow = 0\n",
    "        fast = 0\n",
    "        time = 0\n",
    "        while fast<n-1:\n",
    "            fast+=1\n",
    "            if nums[slow]>nums[fast]:\n",
    "                if time==0:\n",
    "                    if slow>=1 and nums[fast]>nums[slow-1]:\n",
    "                        nums[slow] = nums[fast]\n",
    "                    elif slow>=1 and nums[fast]<nums[slow-1]:\n",
    "                        nums[fast] = nums[slow]\n",
    "                    time+=1\n",
    "\n",
    "                else:\n",
    "                    return False\n",
    "            slow=fast\n",
    "        return True\n",
    "                \n",
    "            \n",
    "                \n",
    "\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
